package exp4;

public class AvlTree<Anytype extends Comparable<? super Anytype>> {
    public AvlNode root;
    public int yezi = 0;

    public int number = 0;

    public void insert(Anytype x) {
        root = insert(x, root);
    }

    private AvlNode<Anytype> insert(Anytype x, AvlNode<Anytype> t) {
        if (t == null) {
            return new AvlNode<>(x);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        }
        return balance(t);
    }

    private AvlNode<Anytype> balance(AvlNode<Anytype> t) {
        if (t == null)
            return t;
        if (height(t.left) - height(t.right) > 1)
            if (height(t.left.left) >= height(t.left.right))
                t = rotateWithLeftChild(t);
            else
                t = doubleWithLeftChild(t);
        else if (height(t.right) - height(t.left) > 1)
            if (height(t.right.right) >= height(t.right.left))
                t = rotateWithRightChild(t);
            else
                t = doubleWithRightChild(t);
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

    private AvlNode<Anytype> rotateWithLeftChild(AvlNode<Anytype> k2) {
        AvlNode<Anytype> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height) + 1;
        return k1;
    }

    private AvlNode<Anytype> rotateWithRightChild(AvlNode<Anytype> k2) {
        AvlNode<Anytype> k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.right), k2.height) + 1;
        return k1;
    }

    private AvlNode<Anytype> doubleWithLeftChild(AvlNode<Anytype> k3) {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    private AvlNode<Anytype> doubleWithRightChild(AvlNode<Anytype> k3) {
        k3.right = rotateWithLeftChild(k3.right);
        return rotateWithRightChild(k3);
    }

    private int height(AvlNode<Anytype> t) {
        return t == null ? -1 : t.height;
    }

    public void calculate(AvlNode<Anytype> B) {
        if (B == null) {
            return;
        }
        if (B.left == null && B.right == null) {
            yezi++;
        } else {
            calculate(B.left);
            calculate(B.right);
        }
    }

    public void preorder(AvlNode<Anytype> B) {
        if (B != null) {
            System.out.printf(B.element + " ");
            preorder(B.left);
            preorder(B.right);
        }
    }

    public void inorder(AvlNode<Anytype> B) {
        if (B != null) {
            inorder(B.left);
            System.out.printf(B.element + " ");
            inorder(B.right);
        }
    }

    public void postorder(AvlNode<Anytype> B) {
        if (B != null) {
            postorder(B.left);
            postorder(B.right);
            System.out.printf(B.element + " ");
        }
    }

    public int shugao(AvlNode<Anytype> B, int shendu) {
        if (B == null) {
            return shendu - 1;
        }
        int left = shugao(B.left, shendu + 1);
        int right = shugao(B.right, shendu + 1);
        return Math.max(left, right);
    }

    public int number(AvlNode<Anytype> B) {
        if (B != null) {
            number++;
            number(B.left);
            number(B.right);
        }
        return number;
    }

    public class AvlNode<Anytype> {
        Anytype element;
        AvlNode<Anytype> left;
        AvlNode<Anytype> right;
        int height;

        AvlNode(Anytype element) {
            this.element = element;
        }
    }
    public boolean search(Anytype t) {
        AvlNode<Anytype> current = root;
        while (true) {
            if (current.element.compareTo(t) > 0) {
                if (current.left == null) {
                    return false;
                }
                current = current.left;
            } else if (current.element.compareTo(t) < 0) {
                if (current.right == null) {
                    return false;
                }
                current = current.right;
            } else {
                return true;
            }
        }
    }
}